/*
 * @lc app=leetcode.cn id=1658 lang=typescript
 *
 * [1658] 将 x 减到 0 的最小操作数
 */

// @lc code=start
function minOperations(nums: number[], x: number): number {
  const n = nums.length;

  const left = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    left[i] = left[i - 1] + nums[i - 1];
  }

  const right = new Array(n + 1).fill(0);
  for (let i = n; i > 0; i--) {
    right[n - i + 1] = right[n - i] + nums[i - 1];
  }

  const binarySearch = (nums: number[], target: number): number => {
    let head = 0;
    let tail = nums.length - 1;
    let mid: number;

    while (head <= tail) {
      mid = head + ((tail - head) >> 1);
      if (nums[mid] === target) return mid;
      if (nums[mid] < target) head = mid + 1;
      else tail = mid - 1;
    }

    return -1;
  };

  let result = -1;
  // 遍历左区间和
  for (let i = 0; i < left.length; i++) {
    const target = x - left[i];
    const j = binarySearch(right, target);
    // 没找到
    if (j === -1) continue;
    // 超出范围了
    if (i + j > n) continue;
    // 更新结果
    result = result === -1 ? i + j : Math.min(result, i + j);
  }

  return result;
}
// @lc code=end
